mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, especially

order theory Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intr ...

, a prefix ordered set generalizes the intuitive concept of a

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

by introducing the possibility of continuous progress and continuous branching. Natural prefix orders often occur when considering

dynamical systems In mathematics, a dynamical system is a system in which a function describes the time dependence of a point in an ambient space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in a ...

as a set of functions from ''time'' (a totally-ordered set) to some

phase space In dynamical system theory, a phase space is a space in which all possible states of a system are represented, with each possible state corresponding to one unique point in the phase space. For mechanical systems, the phase space usuall ...

. In this case, the elements of the set are usually referred to as ''executions'' of the system. The name ''prefix order'' stems from the prefix order on words, which is a special kind of

substring In formal language theory and computer science, a substring is a contiguous sequence of characters within a string. For instance, "''the best of''" is a substring of "''It was the best of times''". In contrast, "''Itwastimes''" is a subsequenc ...

relation and, because of its discrete character, a tree.

Formal definition

A prefix order is a

binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and in ...

"≤" over a

set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...

''P'' which is antisymmetric, transitive, reflexive, and downward total, i.e., for all ''a'', ''b'', and ''c'' in ''P'', we have that: *''a ≤ a'' (reflexivity); *if ''a ≤ b'' and ''b ≤ a'' then ''a'' = ''b'' (antisymmetry); *if ''a ≤ b'' and ''b ≤ c'' then ''a ≤ c'' (transitivity); *if ''a ≤ c'' and ''b ≤ c'' then ''a ≤ b'' or ''b ≤ a'' (downward totality).

Functions between prefix orders

While between partial orders it is usual to consider order-preserving functions, the most important type of functions between prefix orders are so-called history preserving functions. Given a prefix ordered set ''P'', a history of a point ''p''∈''P'' is the (by definition totally ordered) set ''p''− = . A function ''f'': ''P'' → ''Q'' between prefix orders ''P'' and ''Q'' is then history preserving if and only if for every ''p''∈''P'' we find ''f''(''p''−) = ''f''(''p'')−. Similarly, a future of a point ''p''∈''P'' is the (prefix ordered) set ''p''+ = and ''f'' is future preserving if for all ''p''∈''P'' we find ''f''(''p''+) = ''f''(''p'')+. Every history preserving function and every future preserving function is also order preserving, but not vice versa. In the theory of dynamical systems, history preserving maps capture the intuition that the behavior in one system is a ''refinement'' of the behavior in another. Furthermore, functions that are history and future preserving surjections capture the notion of

bisimulation In theoretical computer science a bisimulation is a binary relation between state transition systems, associating systems that behave in the same way in that one system simulates the other and vice versa. Intuitively two systems are bisimilar if ...

between systems, and thus the intuition that a given refinement is ''correct'' with respect to a specification. The

range Range may refer to: Geography * Range (geographic), a chain of hills or mountains; a somewhat linear, complex mountainous or hilly area (cordillera, sierra) ** Mountain range, a group of mountains bordered by lowlands * Range, a term used to i ...

of a history preserving function is always a

prefix closed In computer science, in the area of formal language theory, frequent use is made of a variety of string functions; however, the notation used is different from that used for computer programming, and some commonly used functions in the theoretical ...

subset, where a subset ''S ⊆ P'' is prefix closed if for all ''s,t ∈ P'' with ''t∈S'' and ''s≤t'' we find ''s∈S''.

Product and union

Taking history preserving maps as ''morphisms'' in the

category Category, plural categories, may refer to: Philosophy and general uses * Categorization, categories in cognitive science, information science and generally *Category of being * ''Categories'' (Aristotle) *Category (Kant) *Categories (Peirce) * ...

of prefix orders leads to a notion of product that is ''not'' the Cartesian product of the two orders since the Cartesian product is not always a prefix order. Instead, it leads to an ''arbitrary interleaving'' of the original prefix orders. The union of two prefix orders is the

disjoint union In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A (th ...

, as it is with partial orders.

Isomorphism

Any bijective history preserving function is an

order isomorphism In the mathematical field of order theory, an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets (posets). Whenever two posets are order isomorphic, they can be cons ...

. Furthermore, if for a given prefix ordered set ''P'' we construct the set ''P- ≜ '' we find that this set is prefix ordered by the subset relation ⊆, and furthermore, that the function ''max: P- → P'' is an isomorphism, where ''max(S)'' returns for each set ''S∈P-'' the maximum element in terms of the order on P (i.e. ''max(p-) ≜ p'').

References

* * * {{Order theory Dynamical systems Order theory Trees (data structures)